#include<iostream>
#include<vector>
using namespace std;

//1143.最长公共子序列
int longestCommonSubsequence(string s1, string s2){
    int m = s1.size(), n = s2.size();

    //状态表示 dp[i][j]表示s1[0,i]区间和s2[0,j]区间的所有公共子序列中，最长的公共子序列长度
    //添加第0行和第0列，表示空字符串
    //初始化为0
    vector<vector<int>> dp(m + 1, vector<int>(n + 1));
    
    //使下标映射正确
    s1 = ' ' + s1;
    s2 = ' ' + s2;

    //填表
    for (int i = 1; i <= m; i++){
        for (int j = 1; j <= n; j++){
            //状态转移方程 分情况讨论
            if (s1[i] == s2[j]){
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }
            else{
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    //返回值
    return dp[m][n];
}

//1035.不相交的线
int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2){
    int m = nums1.size(), n = nums2.size();

    //状态表示 dp[i][j]表示nums1区间[0,i]和nums2区间[0,j]可以连线的个数
    //初始化 初始值设置为0
    vector<vector<int>> dp(m + 1, vector<int>(n + 1));

    //填表
    for (int i = 1; i <= m; i++){
        for (int j = 1; j <= n; j++){
            //状态转移方程 分情况讨论
            if (nums1[i - 1] == nums2[j - 1]){
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }
            else{
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    //返回值
    return dp[m][n];
}


//115.不同子序列
const int num = 1000000007;
int numDistinct(string s, string t){
    int m = s.size(), n = t.size();

    //状态表示 dp[i][j]表示s区间[0,j]内的所有子序列中有多少个和t区间[0,i]的子串相等
    //初始化 添加第0行和第0列 第0行表示t字符串为空，则s字符串中一定存在一个子序列空串与t字符串相等,第0行初始值设置为1
    //第0列表示s字符串为空，则s字符串一定不存在子序列与t字符串相等，第0列初始值设置为0
    vector<vector<int>> dp(n + 1, vector<int>(m + 1));
    for (int i = 0; i <= m; i++){
        dp[0][i] = 1;
    }

    //填表
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            //如果不包含当前s[j]字符
            dp[i][j] = dp[i][j - 1];

            //如果包含当前s[j]字符 需要先判断是否相等
            if (s[j - 1] == t[i - 1]){
                dp[i][j] += dp[i - 1][j - 1];
            }

            dp[i][j] %= num;
        }
    }

    //返回值
    return dp[n][m];
}


//44.通配符匹配
bool isMatch(string s, string p){
    int m = s.size(), n = p.size();

    //状态表示 dp[i][j]表示p[0,j]区间的子串能否匹配s[0,i]区间的子串
    vector<vector<bool>> dp(m + 1, vector<bool>(n + 1,false));

    //使下标映射正确
    s = " " + s;
    p = " " + p;

    //初始化
    dp[0][0] = true;
    for (int j = 1; j <= n; j++){
        if(p[j]=='*'){
            dp[0][j] = true;
        }
        else{
            break;
        }
    }

    //填表
    for (int i = 1; i <= m; i++){
        for (int j = 1; j <= n; j++){
            //状态转移方程 分情况讨论
            if (p[j] == '*'){
                dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
            }
            else{
                dp[i][j] = (p[j] == '?' || p[j] == s[i]) && dp[i - 1][j - 1];
            }
        }
    }

    //返回值
    return dp[m][n];
}


//10.正则表达式
bool isMatch(string s, string p){
    int m = s.size(), n = p.size();

    //状态表示 dp[i][j]表示p[0,j]区间的子串能否匹配s[0,i]区间的子串
    //添加第0行和第0列表示两个字符串为空的情况
    vector<vector<bool>> dp(m + 1, vector<bool>(n + 1));

    //使下标映射正确
    s = " " + s;
    p = " " + p;

    //初始化
    dp[0][0] = true;
    for (int j = 2; j <= n; j += 2){
        if (p[j] == '*'){
            dp[0][j] = true;
        }
        //遇到非星号直接结束，剩余全为false
        else{
            break;
        }
    }

    //填表
    for (int i = 1; i <= m; i++){
        for (int j = 1; j <= n; j++){
            //状态转移方程 分情况讨论
            if (p[j] == '*'){
                dp[i][j] = dp[i][j - 2] || (p[j - 1] == '.' || p[j - 1] == s[i]) && dp[i - 1][j];
            }
            else{
                dp[i][j] = (p[j] == '.' || p[j] == s[i]) && dp[i - 1][j - 1];
            }
        }
    }

    //返回值
    return dp[m][n];
}

int main(){


    return 0;
}
